home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 1997 #1 / Amiga Plus CD - 1997 - No. 01.iso / pd / programmierung / mesa-1.2.8 / src-glu / polytest.c < prev    next >
C/C++ Source or Header  |  1996-05-27  |  27KB  |  1,034 lines
  1. /* polytest.c */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  1.2
  6.  * Copyright (C) 1995  Brian Paul  (brianp@ssec.wisc.edu)
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25. $Id: polytest.c,v 1.7 1995/09/05 17:46:20 brianp Exp $
  26.  
  27. $Log: polytest.c,v $
  28.  * Revision 1.7  1995/09/05  17:46:20  brianp
  29.  * removed extraneous & from qsort() call
  30.  *
  31.  * Revision 1.6  1995/08/04  13:09:59  brianp
  32.  * include gluP.h to define NULL, just in case
  33.  *
  34.  * Revision 1.5  1995/07/28  21:35:49  brianp
  35.  * changed all GLUenum to GLenum
  36.  *
  37.  * Revision 1.4  1995/06/09  16:41:07  brianp
  38.  * renamed as polytest.c
  39.  *
  40.  * Revision 1.3  1995/05/23  17:37:48  brianp
  41.  * added #ifndef NULL ...
  42.  *
  43.  * Revision 1.2  1995/05/22  16:56:20  brianp
  44.  * Release 1.2
  45.  *
  46.  * Revision 1.1  1995/04/28  16:20:28  brianp
  47.  * Initial revision
  48.  *
  49.  */
  50.  
  51.  
  52. /*
  53.  * This file is part of the polygon tesselation code contributed by
  54.  * Bogdan Sikorski
  55.  */
  56.  
  57.  
  58. #include <math.h>
  59. #include <stdlib.h>
  60. #include "gluP.h"
  61. #include "tess.h"
  62.  
  63.  
  64.  
  65. static GLenum store_polygon_as_contour(GLUtriangulatorObj *);
  66. static void free_current_polygon(tess_polygon *);
  67. static void prepare_projection_info(GLUtriangulatorObj *);
  68. static GLdouble twice_the_polygon_area(tess_vertex *,tess_vertex *);
  69. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
  70. void tess_find_contour_hierarchies(GLUtriangulatorObj *);
  71. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *);
  72. static GLenum contours_overlap(tess_contour *, tess_polygon *);
  73. static GLenum is_contour_contained_in(tess_contour *,tess_contour *);
  74. static void add_new_exterior(GLUtriangulatorObj *,tess_contour *);
  75. static void add_new_interior(GLUtriangulatorObj *,tess_contour *,
  76.     tess_contour *);
  77. static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
  78.     tess_contour *,tess_contour *);
  79. static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
  80.     tess_contour *,tess_contour *);
  81. static GLboolean point_in_polygon(tess_contour *,GLdouble,GLdouble);
  82. static void shift_interior_to_exterior(GLUtriangulatorObj *,tess_contour *);
  83. static void add_exterior_with_check(GLUtriangulatorObj *,tess_contour *,
  84.     tess_contour *);
  85. static GLenum cut_out_hole(GLUtriangulatorObj *,tess_contour *,
  86.     tess_contour *);
  87. static GLenum merge_hole_with_contour(GLUtriangulatorObj *,
  88.     tess_contour *,tess_contour *,tess_vertex *,
  89.     tess_vertex *);
  90.  
  91. static GLenum
  92. find_normal(GLUtriangulatorObj *tobj)
  93. {
  94.     tess_polygon *polygon=tobj->current_polygon;
  95.     tess_vertex *va,*vb,*vc;
  96.     GLdouble A,B,C;
  97.     GLdouble A0,A1,A2,B0,B1,B2;
  98.  
  99.     va=polygon->vertices;
  100.     vb=va->next;
  101.     A0=vb->location[0]-va->location[0];
  102.     A1=vb->location[1]-va->location[1];
  103.     A2=vb->location[2]-va->location[2];
  104.     for(vc=vb->next;vc!=va;vc=vc->next)
  105.     {
  106.         B0=vc->location[0]-va->location[0];
  107.         B1=vc->location[1]-va->location[1];
  108.         B2=vc->location[2]-va->location[2];
  109.         A=A1*B2-A2*B1;
  110.         B=A2*B0-A0*B2;
  111.         C=A0*B1-A1*B0;
  112.         if(fabs(A)>EPSILON || fabs(B)>EPSILON || fabs(C)>EPSILON)
  113.         {
  114.             polygon->A=A;
  115.             polygon->B=B;
  116.             polygon->C=C;
  117.             polygon->D= -A*va->location[0]-B*va->location[1]-C*va->location[2];
  118.             return GLU_NO_ERROR;
  119.         }
  120.     }
  121.     tess_call_user_error(tobj,GLU_TESS_ERROR7);
  122.     return GLU_ERROR;
  123. }
  124.  
  125. void
  126. tess_test_polygon( GLUtriangulatorObj *tobj )
  127. {
  128.     tess_polygon *polygon=tobj->current_polygon;
  129.  
  130.     /* any vertices defined? */
  131.     if(polygon->vertex_cnt<3)
  132.     {
  133.         free_current_polygon(polygon);
  134.         return;
  135.     }
  136.     /* wrap pointers */
  137.     polygon->last_vertex->next=polygon->vertices;
  138.     polygon->vertices->previous=polygon->last_vertex;
  139.     /* determine the normal */
  140.     if(find_normal(tobj)==GLU_ERROR)
  141.         return;
  142.     /* compare the normals of previously defined contours and this one */
  143.     /* first contour define ? */
  144.     if(tobj->contours==NULL)
  145.     {
  146.         tobj->A=polygon->A;
  147.         tobj->B=polygon->B;
  148.         tobj->C=polygon->C;
  149.         tobj->D=polygon->D;
  150.         /* determine the best projection to use */
  151.         if(fabs(polygon->A) > fabs(polygon->B))
  152.             if(fabs(polygon->A) > fabs(polygon->C))
  153.                 tobj->projection=OYZ;
  154.             else
  155.                 tobj->projection=OXY;
  156.         else
  157.             if(fabs(polygon->B) > fabs(polygon->C))
  158.                 tobj->projection=OXZ;
  159.             else
  160.                 tobj->projection=OXY;
  161.     }
  162.     else
  163.     {
  164.         GLdouble a[3],b[3];
  165.         tess_vertex *vertex=polygon->vertices;
  166.  
  167.         a[0]=tobj->A;
  168.         a[1]=tobj->B;
  169.         a[2]=tobj->C;
  170.         b[0]=polygon->A;
  171.         b[1]=polygon->B;
  172.         b[2]=polygon->C;
  173.  
  174.         /* compare the normals */
  175.         if( fabs(a[1]*b[2]-a[2]*b[1]) > EPSILON ||
  176.             fabs(a[2]*b[0]-a[0]*b[2]) > EPSILON ||
  177.             fabs(a[0]*b[1]-a[1]*b[0]) > EPSILON)
  178.         {
  179.             /* not coplanar */
  180.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  181.             return;
  182.         }
  183.         /* the normals are parallel - test for plane equation */
  184.         if(fabs(a[0]*vertex->location[0]+a[1]*vertex->location[1]+
  185.             a[2]*vertex->location[2]+tobj->D) > EPSILON)
  186.         {
  187.             /* not the same plane */
  188.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  189.             return;
  190.         }
  191.     }
  192.     prepare_projection_info(tobj);
  193.     if(verify_edge_vertex_intersections(tobj)==GLU_ERROR)
  194.         return;
  195.     if(test_for_overlapping_contours(tobj)==GLU_ERROR)
  196.         return;
  197.     if(store_polygon_as_contour(tobj)==GLU_ERROR)
  198.         return;
  199. }
  200.  
  201. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *tobj)
  202. {
  203.     tess_contour *contour;
  204.     tess_polygon *polygon;
  205.  
  206.     polygon=tobj->current_polygon;
  207.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  208.         if(contours_overlap(contour,polygon)!=GLU_NO_ERROR)
  209.         {
  210.             tess_call_user_error(tobj,GLU_TESS_ERROR5);
  211.             return GLU_ERROR;
  212.         }
  213.     return GLU_NO_ERROR;
  214. }
  215.  
  216. static GLenum store_polygon_as_contour(GLUtriangulatorObj *tobj)
  217. {
  218.     tess_polygon *polygon=tobj->current_polygon;
  219.     tess_contour *contour=tobj->contours;
  220.  
  221.     /* the first contour defined */
  222.     if(contour==NULL)
  223.     {
  224.         if((contour=(tess_contour *)malloc(
  225.             sizeof(tess_contour)))==NULL)
  226.         {
  227.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  228.             free_current_polygon(polygon);
  229.             return GLU_ERROR;
  230.         }
  231.         tobj->contours=tobj->last_contour=contour;
  232.         contour->next=contour->previous=NULL;
  233.     }
  234.     else
  235.     {
  236.         if((contour=(tess_contour *)malloc(
  237.             sizeof(tess_contour)))==NULL)
  238.         {
  239.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  240.             free_current_polygon(polygon);
  241.             return GLU_ERROR;
  242.         }
  243.         contour->previous=tobj->last_contour;
  244.         tobj->last_contour->next=contour;
  245.         tobj->last_contour=contour;
  246.         contour->next=NULL;
  247.     }
  248.     /* mark all vertices in new contour as not special */
  249.     /* and all are boundary edges */
  250.     {
  251.         tess_vertex *vertex;
  252.         GLuint vertex_cnt,i;
  253.  
  254.         for(vertex=polygon->vertices , i=0 , vertex_cnt=polygon->vertex_cnt;
  255.             i<vertex_cnt;
  256.             vertex=vertex->next , i++)
  257.         {
  258.             vertex->shadow_vertex=NULL;
  259.             vertex->edge_flag=GL_TRUE;
  260.         }
  261.     }
  262.     contour->vertex_cnt=polygon->vertex_cnt;
  263.     contour->area=polygon->area;
  264.     contour->orientation=polygon->orientation;
  265.     contour->type=GLU_UNKNOWN;
  266.     contour->vertices=polygon->vertices;
  267.     contour->last_vertex=polygon->last_vertex;
  268.     polygon->vertices=polygon->last_vertex=NULL;
  269.     polygon->vertex_cnt=0;
  270.     ++(tobj->contour_cnt);
  271.     return GLU_NO_ERROR;
  272. }
  273.  
  274. static void free_current_polygon(tess_polygon *polygon)
  275. {
  276.     tess_vertex *vertex,*vertex_tmp;
  277.  
  278.     /* free current_polygon structures */
  279.     for(vertex=polygon->vertices;vertex!=polygon->last_vertex;)
  280.     {
  281.         vertex_tmp=vertex->next;
  282.         free(vertex);
  283.         vertex=vertex_tmp;
  284.     }
  285.     polygon->vertices=polygon->last_vertex=NULL;
  286.     polygon->vertex_cnt=0;
  287. }
  288.  
  289. static void prepare_projection_info(GLUtriangulatorObj *tobj)
  290. {
  291.     tess_polygon *polygon=tobj->current_polygon;
  292.     tess_vertex *vertex,*last_vertex_ptr;
  293.     GLdouble area;
  294.  
  295.     last_vertex_ptr=polygon->last_vertex;
  296.     switch(tobj->projection)
  297.     {
  298.         case OXY:
  299.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  300.                 vertex=vertex->next)
  301.             {
  302.                 vertex->x=vertex->location[0];
  303.                 vertex->y=vertex->location[1];
  304.             }
  305.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  306.             last_vertex_ptr->y=last_vertex_ptr->location[1];
  307.             break;
  308.         case OXZ:
  309.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  310.                 vertex=vertex->next)
  311.             {
  312.                 vertex->x=vertex->location[0];
  313.                 vertex->y=vertex->location[2];
  314.             }
  315.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  316.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  317.             break;
  318.         case OYZ:
  319.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  320.                 vertex=vertex->next)
  321.             {
  322.                 vertex->x=vertex->location[1];
  323.                 vertex->y=vertex->location[2];
  324.             }
  325.             last_vertex_ptr->x=last_vertex_ptr->location[1];
  326.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  327.             break;
  328.     }
  329.     area=twice_the_polygon_area(polygon->vertices,polygon->last_vertex);
  330.     if(area >= 0.0)
  331.     {
  332.         polygon->orientation=GLU_CCW;
  333.         polygon->area=area;
  334.     }
  335.     else
  336.     {
  337.         polygon->orientation=GLU_CW;
  338.         polygon->area= -area;
  339.     }
  340. }
  341.  
  342. static GLdouble twice_the_polygon_area(tess_vertex *vertex,
  343.     tess_vertex *last_vertex)
  344. {
  345.     tess_vertex *next;
  346.     GLdouble area,x,y;
  347.  
  348.     area=0.0;
  349.     x=vertex->x;
  350.     y=vertex->y;
  351.     vertex=vertex->next;
  352.     for(; vertex!=last_vertex; vertex=vertex->next)
  353.     {
  354.         next=vertex->next;
  355.         area+=(vertex->x - x)*(next->y - y) - (vertex->y - y)*(next->x - x);
  356.     }
  357.     return area;
  358. }
  359.  
  360. /* test if edges ab and cd intersect */
  361. /* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
  362. /* else if adjacent return GLU_TESS_ERROR4 */
  363. static GLenum edge_edge_intersect(
  364.     tess_vertex *a,
  365.     tess_vertex *b,
  366.     tess_vertex *c,
  367.     tess_vertex *d)
  368. {
  369.     GLdouble denom,r,s;
  370.     GLdouble xba,ydc,yba,xdc,yac,xac;
  371.  
  372.     xba=b->x - a->x;
  373.     yba=b->y - a->y;
  374.     xdc=d->x - c->x;
  375.     ydc=d->y - c->y;
  376.     xac=a->x - c->x;
  377.     yac=a->y - c->y;
  378.     denom= xba*ydc - yba*xdc;
  379.     r = yac*xdc - xac*ydc;
  380.     /* parallel? */
  381.     if(fabs(denom) < EPSILON)
  382.     {
  383.         if(fabs(r) < EPSILON)
  384.         {
  385.             /* colinear */
  386.             if(fabs(xba) < EPSILON)
  387.             {
  388.                 /* compare the Y coordinate */
  389.                 if(yba > 0.0)
  390.                 {
  391.                     if((fabs(a->y - c->y)<EPSILON && fabs(c->y - b->y)<EPSILON)
  392.                         ||
  393.                         (fabs(a->y - d->y)<EPSILON && fabs(d->y - b->y)<EPSILON))
  394.                     return GLU_TESS_ERROR4;
  395.  
  396.                 }
  397.                 else
  398.                 {
  399.                     if((fabs(b->y - c->y)<EPSILON && fabs(c->y - a->y)<EPSILON)
  400.                         ||
  401.                         (fabs(b->y - d->y)<EPSILON && fabs(d->y - a->y)<EPSILON))
  402.                     return GLU_TESS_ERROR4;
  403.                 }
  404.             }
  405.             else
  406.             {
  407.                 /* compare the X coordinate */
  408.                 if(xba > 0.0)
  409.                 {
  410.                     if((fabs(a->x - c->x)<EPSILON && fabs(c->x - b->x)<EPSILON)
  411.                         ||
  412.                         (fabs(a->x - d->x)<EPSILON && fabs(d->x - b->x)<EPSILON))
  413.                     return GLU_TESS_ERROR4;
  414.                 }
  415.                 else
  416.                 {
  417.                     if((fabs(b->x - c->x)<EPSILON && fabs(c->x - a->x)<EPSILON)
  418.                         ||
  419.                         (fabs(b->x - d->x)<EPSILON && fabs(d->x - a->x)<EPSILON))
  420.                     return GLU_TESS_ERROR4;
  421.                 }
  422.             }
  423.         }
  424.         return GLU_NO_ERROR;
  425.     }
  426.     r /= denom;
  427.     s = (yac*xba - xac*yba) / denom;
  428.     /* test if one vertex lies on other edge */
  429.     if(((fabs(r) < EPSILON || (r < 1.0+EPSILON && r > 1.0-EPSILON)) &&
  430.         s > -EPSILON && s < 1.0+EPSILON) ||
  431.         ((fabs(s) < EPSILON || (s < 1.0+EPSILON && s > 1.0-EPSILON)) &&
  432.         r > -EPSILON && r < 1.0+EPSILON))
  433.     {
  434.         return GLU_TESS_ERROR4;
  435.     }
  436.     /* test for crossing */
  437.     if(r > -EPSILON && r < 1.0+EPSILON &&
  438.         s > -EPSILON && s < 1.0+EPSILON)
  439.     {
  440.         return GLU_TESS_ERROR8;
  441.     }
  442.     return GLU_NO_ERROR;
  443. }
  444.  
  445. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *tobj)
  446. {
  447.     tess_polygon *polygon=tobj->current_polygon;
  448.     tess_vertex *vertex1,*last_vertex,*vertex2;
  449.     GLenum test;
  450.  
  451.     last_vertex=polygon->last_vertex;
  452.     vertex1=last_vertex;
  453.     for(vertex2=vertex1->next->next;
  454.         vertex2->next!=last_vertex;
  455.         vertex2=vertex2->next)
  456.     {
  457.         test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  458.             vertex2->next);
  459.         if(test!=GLU_NO_ERROR)
  460.         {
  461.             tess_call_user_error(tobj,test);
  462.             return GLU_ERROR;
  463.         }
  464.     }
  465.     for(vertex1=polygon->vertices;
  466.         vertex1->next->next!=last_vertex;
  467.         vertex1=vertex1->next)
  468.     {
  469.         for(vertex2=vertex1->next->next;
  470.             vertex2!=last_vertex;
  471.             vertex2=vertex2->next)
  472.         {
  473.             test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  474.                 vertex2->next);
  475.             if(test!=GLU_NO_ERROR)
  476.             {
  477.                 tess_call_user_error(tobj,test);
  478.                 return GLU_ERROR;
  479.             }
  480.         }
  481.     }
  482.     return GLU_NO_ERROR;
  483. }
  484.  
  485. static int area_compare(const void *a,const void *b)
  486. {
  487.     GLdouble area1,area2;
  488.  
  489.     area1=(*((tess_contour **)a))->area;
  490.     area2=(*((tess_contour **)b))->area;
  491.     if(area1 < area2)
  492.         return 1;
  493.     if(area1 > area2)
  494.         return -1;
  495.     return 0;
  496. }
  497.  
  498. void tess_find_contour_hierarchies(GLUtriangulatorObj *tobj)
  499. {
  500.     tess_contour **contours; /* dinamic array of pointers */
  501.     tess_contour *tmp_contour_ptr=tobj->contours;
  502.     GLuint cnt,i;
  503.     GLenum result;
  504.     GLboolean hierarchy_changed;
  505.  
  506.     /* any contours? */
  507.     if(tobj->contour_cnt < 2)
  508.     {
  509.         tobj->contours->type=GLU_EXTERIOR;
  510.         return;
  511.     }
  512.     if((contours=(tess_contour **)
  513.         malloc(sizeof(tess_contour *)*(tobj->contour_cnt)))==NULL)
  514.     {
  515.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  516.         return;
  517.     }
  518.     for(tmp_contour_ptr=tobj->contours , cnt=0;
  519.         tmp_contour_ptr!=NULL;
  520.         tmp_contour_ptr=tmp_contour_ptr->next)
  521.         contours[cnt++]=tmp_contour_ptr;
  522.     /* now sort the contours in decreasing area size order */
  523.     qsort((void *)contours,(size_t)cnt,(size_t)sizeof(tess_contour *),area_compare);
  524.     /* we leave just the first contour - remove others from list */
  525.     tobj->contours=contours[0];
  526.     tobj->contours->next=tobj->contours->previous=NULL;
  527.     tobj->last_contour=tobj->contours;
  528.     tobj->contour_cnt=1;
  529.     /* first contour is the one with greatest area */
  530.     /* must be EXTERIOR */
  531.     tobj->contours->type=GLU_EXTERIOR;
  532.     tmp_contour_ptr=tobj->contours;
  533.     /* now we play! */
  534.     for(i=1;i<cnt;i++)
  535.     {
  536.         hierarchy_changed=GL_FALSE;
  537.         for(tmp_contour_ptr=tobj->contours;
  538.             tmp_contour_ptr!=NULL;
  539.             tmp_contour_ptr=tmp_contour_ptr->next)
  540.         {
  541.             if(tmp_contour_ptr->type==GLU_EXTERIOR)
  542.             {
  543.                 /* check if contour completely contained in EXTERIOR */
  544.                 result=is_contour_contained_in(tmp_contour_ptr,contours[i]);
  545.                 switch(result)
  546.                 {
  547.                     case GLU_INTERIOR:
  548.                         /* now we have to check if contour is inside interiors */
  549.                         /* or not */
  550.                         /* any interiors? */
  551.                         if(tmp_contour_ptr->next!=NULL &&
  552.                             tmp_contour_ptr->next->type==GLU_INTERIOR)
  553.                         {
  554.                             /* for all interior, check if inside any of them */
  555.                             /* if not inside any of interiors, its another */
  556.                             /* interior */
  557.                             /* or it may contain some interiors, then change */
  558.                             /* the contained interiors to exterior ones */
  559.                             add_interior_with_hierarchy_check(tobj,
  560.                                 tmp_contour_ptr,contours[i]);
  561.                         }
  562.                         else
  563.                         {
  564.                             /* not in interior, add as new interior contour */
  565.                             add_new_interior(tobj,tmp_contour_ptr,contours[i]);
  566.                         }
  567.                         hierarchy_changed=GL_TRUE;
  568.                         break;
  569.                     case GLU_EXTERIOR:
  570.                         /* ooops, the marked as EXTERIOR (contours[i]) is */
  571.                         /* actually an interior of tmp_contour_ptr */
  572.                         /*  reverse the local hierarchy */
  573.                         reverse_hierarchy_and_add_exterior(tobj,tmp_contour_ptr,
  574.                             contours[i]);
  575.                         hierarchy_changed=GL_TRUE;
  576.                         break;
  577.                     case GLU_NO_ERROR:
  578.                         break;
  579.                 }
  580.             }
  581.             if(hierarchy_changed)
  582.                 break; /* break from for loop */
  583.         }
  584.         if(hierarchy_changed==GL_FALSE)
  585.         {
  586.             /* disjoint with all contours, add to contour list */
  587.             add_new_exterior(tobj,contours[i]);
  588.         }
  589.     }
  590.     free(contours);
  591. }
  592.  
  593. /* returns GLU_INTERIOR if inner is completey enclosed within outer */
  594. /* returns GLU_EXTERIOR if outer is completely enclosed within inner */
  595. /* returns GLU_NO_ERROR if contours are disjoint */
  596. static GLenum is_contour_contained_in(
  597.     tess_contour *outer,
  598.     tess_contour *inner)
  599. {
  600.     GLenum relation_flag;
  601.  
  602.     /* set relation_flag to relation of containment of first inner vertex */
  603.     /* regarding outer contour */
  604.     if(point_in_polygon(outer,inner->vertices->x,inner->vertices->y))
  605.         relation_flag=GLU_INTERIOR;
  606.     else
  607.         relation_flag=GLU_EXTERIOR;
  608.     if(relation_flag==GLU_INTERIOR)
  609.         return GLU_INTERIOR;
  610.     if(point_in_polygon(inner,outer->vertices->x,outer->vertices->y))
  611.         return GLU_EXTERIOR;
  612.     return GLU_NO_ERROR;
  613. }
  614.  
  615. static GLboolean point_in_polygon(
  616.     tess_contour *contour,
  617.     GLdouble x,
  618.     GLdouble y)
  619. {
  620.     tess_vertex *v1,*v2;
  621.     GLuint i,vertex_cnt;
  622.     GLdouble xp1,yp1,xp2,yp2;
  623.     GLboolean tst;
  624.  
  625.     tst=GL_FALSE;
  626.     v1=contour->vertices;
  627.     v2=contour->vertices->previous;
  628.     for(i=0 , vertex_cnt=contour->vertex_cnt;
  629.         i < vertex_cnt;
  630.         i++)
  631.     {
  632.         xp1=v1->x;
  633.         yp1=v1->y;
  634.         xp2=v2->x;
  635.         yp2=v2->y;
  636.         if ((((yp1<=y) && (y<yp2)) || ((yp2<=y)  && (y<yp1))) &&
  637.             (x < (xp2 - xp1) * (y - yp1) /  (yp2 - yp1) + xp1))
  638.                 tst = (tst==GL_FALSE ? GL_TRUE : GL_FALSE);
  639.         v2=v1;
  640.         v1=v1->next;
  641.     }
  642.     return tst;
  643. }
  644.  
  645. static GLenum contours_overlap(
  646.     tess_contour *contour,
  647.     tess_polygon *polygon)
  648. {
  649.     tess_vertex *vertex1,*vertex2;
  650.     GLuint vertex1_cnt,vertex2_cnt,i,j;
  651.     GLenum test;
  652.  
  653.     vertex1=contour->vertices;
  654.     vertex2=polygon->vertices;
  655.     vertex1_cnt=contour->vertex_cnt;
  656.     vertex2_cnt=polygon->vertex_cnt;
  657.     for(i=0; i<vertex1_cnt; vertex1=vertex1->next , i++)
  658.     {
  659.         for(j=0; j<vertex2_cnt; vertex2=vertex2->next , j++)
  660.             if((test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  661.                 vertex2->next))!=GLU_NO_ERROR)
  662.                 return test;
  663.     }
  664.     return GLU_NO_ERROR;
  665. }
  666.  
  667. static void add_new_exterior(
  668.     GLUtriangulatorObj *tobj,
  669.     tess_contour *contour)
  670. {
  671.     contour->type=GLU_EXTERIOR;
  672.     contour->next=NULL;
  673.     contour->previous=tobj->last_contour;
  674.     tobj->last_contour->next=contour;
  675.     tobj->last_contour=contour;
  676. }
  677.  
  678. static void add_new_interior(
  679.     GLUtriangulatorObj *tobj,
  680.     tess_contour *outer,
  681.     tess_contour *contour)
  682. {
  683.     contour->type=GLU_INTERIOR;
  684.     contour->next=outer->next;
  685.     contour->previous=outer;
  686.     if(outer->next!=NULL)
  687.         outer->next->previous=contour;
  688.     outer->next=contour;
  689.     if(tobj->last_contour==outer)
  690.         tobj->last_contour=contour;
  691. }
  692.  
  693. static void add_interior_with_hierarchy_check(
  694.     GLUtriangulatorObj *tobj,
  695.     tess_contour *outer,
  696.     tess_contour *contour)
  697. {
  698.     tess_contour *ptr;
  699.  
  700.     /* for all interiors of outer check if they are interior of contour */
  701.     /* if so, change that interior to exterior and move it of of the */
  702.     /* interior sequence */
  703.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  704.     {
  705.         GLenum test;
  706.  
  707.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  708.         {
  709.             test=is_contour_contained_in(ptr,contour);
  710.             switch(test)
  711.             {
  712.                 case GLU_INTERIOR:
  713.                     /* contour is contained in one of the interiors */
  714.                     /* check if possibly contained in other exteriors */
  715.                     /* move ptr to first EXTERIOR */
  716.                     for(;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next);
  717.                     if(ptr==NULL)
  718.                         /* another exterior */
  719.                         add_new_exterior(tobj,contour);
  720.                     else
  721.                         add_exterior_with_check(tobj,ptr,contour);
  722.                     return;
  723.                 case GLU_EXTERIOR:
  724.                     /* one of the interiors is contained in the contour */
  725.                     /* change it to EXTERIOR, and shift it away from the */
  726.                     /* interior sequence */
  727.                     shift_interior_to_exterior(tobj,ptr);
  728.                     break;
  729.                 case GLU_NO_ERROR:
  730.                     /* disjoint */
  731.                     break;
  732.             }
  733.         }
  734.     }
  735.     /* add contour to the interior sequence */
  736.     add_new_interior(tobj,outer,contour);
  737. }
  738.  
  739. static void reverse_hierarchy_and_add_exterior(
  740.     GLUtriangulatorObj *tobj,
  741.     tess_contour *outer,
  742.     tess_contour *contour)
  743. {
  744.     tess_contour *ptr;
  745.  
  746.     /* reverse INTERIORS to EXTERIORS */
  747.     /* any INTERIORS? */
  748.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  749.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  750.             ptr->type=GLU_EXTERIOR;
  751.     /* the outer now becomes inner */
  752.     outer->type=GLU_INTERIOR;
  753.     /* contour is the EXTERIOR */
  754.     contour->next=outer;
  755.     if(tobj->contours==outer)
  756.     {
  757.         /* first contour beeing reversed */
  758.         contour->previous=NULL;
  759.         tobj->contours=contour;
  760.     }
  761.     else
  762.     {
  763.         outer->previous->next=contour;
  764.         contour->previous=outer->previous;
  765.     }
  766.     outer->previous=contour;
  767. }
  768.  
  769. static void shift_interior_to_exterior(
  770.     GLUtriangulatorObj *tobj,
  771.     tess_contour *contour)
  772. {
  773.     contour->previous->next=contour->next;
  774.     if(contour->next!=NULL)
  775.         contour->next->previous=contour->previous;
  776.     else
  777.         tobj->last_contour=contour->previous;
  778. }
  779.  
  780. static void add_exterior_with_check(
  781.     GLUtriangulatorObj *tobj,
  782.     tess_contour *outer,
  783.     tess_contour *contour)
  784. {
  785.     GLenum test;
  786.  
  787.     /* this contour might be interior to further exteriors - check */
  788.     /* if not, just add as a new exterior */
  789.     for(;outer!=NULL && outer->type==GLU_EXTERIOR;outer=outer->next)
  790.     {
  791.         test=is_contour_contained_in(outer,contour);
  792.         switch(test)
  793.         {
  794.             case GLU_INTERIOR:
  795.                 /* now we have to check if contour is inside interiors */
  796.                 /* or not */
  797.                 /* any interiors? */
  798.                 if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  799.                 {
  800.                     /* for all interior, check if inside any of them */
  801.                     /* if not inside any of interiors, its another */
  802.                     /* interior */
  803.                     /* or it may contain some interiors, then change */
  804.                     /* the contained interiors to exterior ones */
  805.                     add_interior_with_hierarchy_check(tobj,
  806.                         outer,contour);
  807.                 }
  808.                 else
  809.                 {
  810.                     /* not in interior, add as new interior contour */
  811.                     add_new_interior(tobj,outer,contour);
  812.                 }
  813.                 return;
  814.             case GLU_NO_ERROR:
  815.                 /* disjoint */
  816.                 break;
  817.         }
  818.     }
  819.     /* add contour to the exterior sequence */
  820.     add_new_exterior(tobj,contour);
  821. }
  822.  
  823. void tess_handle_holes(GLUtriangulatorObj *tobj)
  824. {
  825.     tess_contour *contour,*hole;
  826.     GLenum exterior_orientation;
  827.  
  828.     /* verify hole orientation */
  829.     for(contour=tobj->contours;contour!=NULL;)
  830.     {
  831.         exterior_orientation=contour->orientation;
  832.         for(contour=contour->next;
  833.             contour!=NULL && contour->type==GLU_INTERIOR;
  834.             contour=contour->next)
  835.         {
  836.             if(contour->orientation==exterior_orientation)
  837.             {
  838.                 tess_call_user_error(tobj,GLU_TESS_ERROR5);
  839.                 return;
  840.             }
  841.         }
  842.     }
  843.     /* now cut-out holes */
  844.     for(contour=tobj->contours;contour!=NULL;)
  845.     {
  846.         hole=contour->next;
  847.         while(hole!=NULL && hole->type==GLU_INTERIOR)
  848.         {
  849.             if(cut_out_hole(tobj,contour,hole)==GLU_ERROR)
  850.                 return;
  851.             hole=contour->next;
  852.         }
  853.         contour=contour->next;
  854.     }
  855. }
  856.  
  857. static GLenum cut_out_hole(
  858.     GLUtriangulatorObj *tobj,
  859.     tess_contour *contour,
  860.     tess_contour *hole)
  861. {
  862.     tess_contour *tmp_hole;
  863.     tess_vertex *v1,*v2,*tmp_vertex;
  864.     GLuint vertex1_cnt,vertex2_cnt,tmp_vertex_cnt;
  865.     GLuint i,j,k;
  866.     GLenum test;
  867.  
  868.     /* find an edge connecting contour and hole not intersecting any other */
  869.     /* edge belonging to either the contour or any of the other holes */
  870.     for(v1=contour->vertices , vertex1_cnt=contour->vertex_cnt , i=0;
  871.         i<vertex1_cnt;
  872.         i++ , v1=v1->next)
  873.     {
  874.         for(v2=hole->vertices , vertex2_cnt=hole->vertex_cnt , j=0;
  875.             j<vertex2_cnt;
  876.             j++ , v2=v2->next)
  877.         {
  878.             /* does edge (v1,v2) intersect any edge of contour */
  879.             for(tmp_vertex=contour->vertices , tmp_vertex_cnt=contour->vertex_cnt ,
  880.                     k=0;
  881.                 k<tmp_vertex_cnt;
  882.                 tmp_vertex=tmp_vertex->next , k++)
  883.             {
  884.                 /* skip edge tests for edges directly connected */
  885.                 if(v1==tmp_vertex || v1==tmp_vertex->next)
  886.                     continue;
  887.                 test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  888.                 if(test!=GLU_NO_ERROR)
  889.                     break;
  890.             }
  891.             if(test==GLU_NO_ERROR)
  892.             {
  893.                 /* does edge (v1,v2) intersect any edge of hole */
  894.                 for(tmp_vertex=hole->vertices ,
  895.                         tmp_vertex_cnt=hole->vertex_cnt , k=0;
  896.                     k<tmp_vertex_cnt;
  897.                     tmp_vertex=tmp_vertex->next , k++)
  898.                 {
  899.                     /* skip edge tests for edges directly connected */
  900.                     if(v2==tmp_vertex || v2==tmp_vertex->next)
  901.                         continue;
  902.                     test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  903.                     if(test!=GLU_NO_ERROR)
  904.                         break;
  905.                 }
  906.                 if(test==GLU_NO_ERROR)
  907.                 {
  908.                     /* does edge (v1,v2) intersect any other hole? */
  909.                     for(tmp_hole=hole->next;
  910.                         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  911.                         tmp_hole=tmp_hole->next)
  912.                     {
  913.                         /* does edge (v1,v2) intersect any edge of hole */
  914.                         for(tmp_vertex=tmp_hole->vertices ,
  915.                                 tmp_vertex_cnt=tmp_hole->vertex_cnt , k=0;
  916.                             k<tmp_vertex_cnt;
  917.                             tmp_vertex=tmp_vertex->next , k++)
  918.                         {
  919.                             test=edge_edge_intersect(v1,v2,tmp_vertex,
  920.                                 tmp_vertex->next);
  921.                             if(test!=GLU_NO_ERROR)
  922.                                 break;
  923.                         }
  924.                         if(test!=GLU_NO_ERROR)
  925.                             break;
  926.                     }
  927.                 }
  928.             }
  929.             if(test==GLU_NO_ERROR)
  930.             {
  931.                 /* edge (v1,v2) is good for eliminating the hole */
  932.                 if(merge_hole_with_contour(tobj,contour,hole,v1,v2)
  933.                     ==GLU_NO_ERROR)
  934.                     return GLU_NO_ERROR;
  935.                 else
  936.                     return GLU_ERROR;
  937.             }
  938.         }
  939.     }
  940.     /* other holes are blocking all possible connections of hole */
  941.     /* with contour, we shift this hole as the last hole and retry */
  942.     for(tmp_hole=hole;
  943.         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  944.         tmp_hole=tmp_hole->next);
  945.     contour->next=hole->next;
  946.     hole->next->previous=contour;
  947.     if(tmp_hole==NULL)
  948.     {
  949.         /* last EXTERIOR contour, shift hole as last contour */
  950.         hole->next=NULL;
  951.         hole->previous=tobj->last_contour;
  952.         tobj->last_contour->next=hole;
  953.         tobj->last_contour=hole;
  954.     }
  955.     else
  956.     {
  957.         tmp_hole->previous->next=hole;
  958.         hole->previous=tmp_hole->previous;
  959.         tmp_hole->previous=hole;
  960.         hole->next=tmp_hole;
  961.     }
  962.     hole=contour->next;
  963.     /* try once again - recurse */
  964.     return cut_out_hole(tobj,contour,hole);
  965. }
  966.  
  967. static GLenum merge_hole_with_contour(
  968.     GLUtriangulatorObj *tobj,
  969.     tess_contour *contour,
  970.     tess_contour *hole,
  971.     tess_vertex *v1,
  972.     tess_vertex *v2)
  973. {
  974.     tess_vertex *v1_new,*v2_new;
  975.  
  976.     /* make copies of v1 and v2, place them respectively after their originals */
  977.     if((v1_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  978.     {
  979.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  980.         return GLU_ERROR;
  981.     }
  982.     if((v2_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  983.     {
  984.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  985.         return GLU_ERROR;
  986.     }
  987.     v1_new->edge_flag=GL_TRUE;
  988.     v1_new->data=v1->data;
  989.     v1_new->location[0]=v1->location[0];
  990.     v1_new->location[1]=v1->location[1];
  991.     v1_new->location[2]=v1->location[2];
  992.     v1_new->x=v1->x;
  993.     v1_new->y=v1->y;
  994.     v1_new->shadow_vertex=v1;
  995.     v1->shadow_vertex=v1_new;
  996.     v1_new->next=v1->next;
  997.     v1_new->previous=v1;
  998.     v1->next->previous=v1_new;
  999.     v1->next=v1_new;
  1000.     v2_new->edge_flag=GL_TRUE;
  1001.     v2_new->data=v2->data;
  1002.     v2_new->location[0]=v2->location[0];
  1003.     v2_new->location[1]=v2->location[1];
  1004.     v2_new->location[2]=v2->location[2];
  1005.     v2_new->x=v2->x;
  1006.     v2_new->y=v2->y;
  1007.     v2_new->shadow_vertex=v2;
  1008.     v2->shadow_vertex=v2_new;
  1009.     v2_new->next=v2->next;
  1010.     v2_new->previous=v2;
  1011.     v2->next->previous=v2_new;
  1012.     v2->next=v2_new;
  1013.     /* link together the two lists */
  1014.     v1->next=v2_new;
  1015.     v2_new->previous=v1;
  1016.     v2->next=v1_new;
  1017.     v1_new->previous=v2;
  1018.     /* update the vertex count of the contour */
  1019.     contour->vertex_cnt += hole->vertex_cnt+2;
  1020.     /* remove the INTERIOR contour */
  1021.     contour->next=hole->next;
  1022.     if(hole->next!=NULL)
  1023.         hole->next->previous=contour;
  1024.     free(hole);
  1025.     /* update tobj structure */
  1026.     --(tobj->contour_cnt);
  1027.     if(contour->last_vertex==v1)
  1028.         contour->last_vertex=v1_new;
  1029.     /* mark two vertices with edge_flag */
  1030.     v2->edge_flag=GL_FALSE;
  1031.     v1->edge_flag=GL_FALSE;
  1032.     return GLU_NO_ERROR;
  1033. }
  1034.